package difficulty;

public class L52 {

    int count = 0;

    public int totalNQueens(int n) {
        //dfs+位运算
        totalNQueens(n, 0,0, 0, 0);
        return count;
    }

    public void totalNQueens(int n,int v, int cols, int pie, int na) {
        if (n == v) {
            count++;
            return;
        }
        int bit = (~(cols | pie | na)) & ((1 << n) - 1);
        while (bit != 0) {
            int p = bit & -bit;
            bit = bit & (bit - 1);
            totalNQueens(n,v+1, cols | p, (pie | p) << 1, (na | p) >> 1);
        }
    }
}